package com.vans.practice.alghr;

import java.util.Arrays;

/**
 * @Description: 归并排序
 * @特点： 稳定啊
 * @平均时间复杂度： nLog2N
 * @空间复杂度： n
 * @Author elle
 * @Date 2020/10/7 15:02
 */
public class Merge {

    public static void main(String[] args) {
//        int[] a = {9,5,2,7,14,1,0,3};
        int[] a = {9, 5, 11,2};
        sort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }

    private static void sort(int[] a, int left, int right) {
        int mid = (left + right) / 2;
        if (left == right) return;
        sort(a, left, mid);
        sort(a, mid + 1, right);
        merge(a, left, mid + 1, right);
    }

    /**
     * 归并
     *
     * @param a
     * @param left
     * @param right
     */
    private static void merge(int[] a, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int k = 0;
        int i = left;
        int j = mid;
        while (i < mid && j <= right) {
            if (a[i] < a[j]) {
                temp[k] = a[i];
                k++;
                i++;
            } else {
                temp[k] = a[j];
                k++;
                j++;
            }
        }
        while(i < mid) temp[k++] = a[i++];
        while(j <= right) temp[k++] = a[j++];
//        System.out.println(Arrays.toString(temp));
        for (int l = 0; l < temp.length; l++) {
            a[left + l] = temp[l];
        }
    }

}
